<!doctype html><html class="use-motion" lang="en"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><meta name="google-site-verification" content="0axhmy0-lA3xPbR8wPgyWlMZjwWSCfagKukdyeCQ7LU"><link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css"><link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css"><link href="/css/main.css?v=5.1.0" rel="stylesheet" type="text/css"><meta name="keywords" content="DPDK,Network,VPP,"><link rel="alternate" href="/atom.xml" title="赵占旭的博客" type="application/atom+xml"><link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.0"><meta name="description" content="注：本文是转载，但不是100%的转载，可能稍微有些出入，原文地址点击这里"><meta name="keywords" content="DPDK,Network,VPP"><meta property="og:type" content="article"><meta property="og:title" content="[转]Cisco VPP 路由分析下"><meta property="og:url" content="http://zhaozhanxu.com/2017/01/10/VPP/2017-01-10-VPP-Router2/index.html"><meta property="og:site_name" content="赵占旭的博客"><meta property="og:description" content="注：本文是转载，但不是100%的转载，可能稍微有些出入，原文地址点击这里"><meta property="og:locale" content="en"><meta property="og:updated_time" content="2017-12-11T14:31:18.945Z"><meta name="twitter:card" content="summary"><meta name="twitter:title" content="[转]Cisco VPP 路由分析下"><meta name="twitter:description" content="注：本文是转载，但不是100%的转载，可能稍微有些出入，原文地址点击这里"><script type="text/javascript" id="hexo.configurations">var NexT=window.NexT||{},CONFIG={root:"/",sidebar:{position:"left",display:"post",offset:342,offset_float:0},fancybox:!0,motion:!0}</script><link rel="canonical" href="http://zhaozhanxu.com/2017/01/10/VPP/2017-01-10-VPP-Router2/"><title> [转]Cisco VPP 路由分析下 | 赵占旭的博客</title></head><body itemscope itemtype="http://schema.org/WebPage" lang="en"><script>!function(e,a,t,c,n,g,o){e.GoogleAnalyticsObject="ga",e.ga=e.ga||function(){(e.ga.q=e.ga.q||[]).push(arguments)},e.ga.l=1*new Date,g=a.createElement("script"),o=a.getElementsByTagName("script")[0],g.async=1,g.src="//www.google-analytics.com/analytics.js",o.parentNode.insertBefore(g,o)}(window,document),ga("create","3a235f2280210fdd34cebc8c3647e5b8","auto"),ga("send","pageview")</script><script type="text/javascript">var _hmt=_hmt||[];!function(){var e=document.createElement("script");e.src="//hm.baidu.com/hm.js?UA-90327054-1";var t=document.getElementsByTagName("script")[0];t.parentNode.insertBefore(e,t)}()</script><script type="text/javascript">!function(){var e=document.createElement("script");e.src="//tajs.qq.com/stats?sId=60806179";var t=document.getElementsByTagName("script")[0];t.parentNode.insertBefore(e,t)}()</script><div class="container one-collumn sidebar-position-left page-post-detail"><div class="headband"></div><header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader" style="background-image:url(/images/public/home_bg.jpg)"><div class="header-cover"><div class="header-inner"><a class="site-home" href="/">赵占旭的博客</a><div class="site-meta"><div class="custom-logo-site-title"><div href="/" class="brand"><span class="logo-line-before"><i></i></span> <span class="site-title">赵占旭的博客</span><span class="logo-line-after"><i></i></span></div></div><h1 class="site-subtitle" itemprop="description">一花一世界 一叶一菩提</h1></div><div class="site-nav-toggle"> <button><span class="btn-bar"></span><span class="btn-bar"></span><span class="btn-bar"></span></button></div><nav class="site-nav"><ul id="menu" class="menu"><li class="menu-item menu-item-categories"><a href="/categories" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i><br> Categories</a></li><li class="menu-item menu-item-tags"><a href="/tags" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i><br> Tags</a></li><li class="menu-item menu-item-archives"><a href="/archives" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i><br> Archives</a></li><li class="menu-item menu-item-about"><a href="/about" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i><br> About</a></li><li class="menu-item menu-item-search"><a href="javascript:" ; class="popup-trigger"><i class="menu-item-icon fa fa-search fa-fw"></i><br> Search</a></li></ul><div class="site-search"><div class="popup local-search-popup"><div class="local-search-header clearfix"><span class="search-icon"><i class="fa fa-search"></i></span><span class="popup-btn-close"><i class="fa fa-times-circle"></i></span><div class="local-search-input-wrapper"> <input autocapitalize="off" autocomplete="off" autocorrect="off" placeholder="search.placeholder" spellcheck="false" type="text" id="local-search-input"></div></div><div id="local-search-result"></div></div></div></nav></div><div class="header-post"><div class="post-header"><div class="tags"> <a href="/tags/DPDK/" rel="tag" title="DPDK">DPDK</a> <a href="/tags/Network/" rel="tag" title="Network">Network</a> <a href="/tags/VPP/" rel="tag" title="VPP">VPP</a></div><h1>[转]Cisco VPP 路由分析下</h1><h2 class="subtitle">Section 15. VPP 路由代码分析</h2><div class="post-time"> <span class="post-meta-item-text">Posted on</span> <time itemprop="dateCreated" datetime="2017-01-10T00:00:00+08:00" content="2017-01-10" title="2017-01-10 00:00:00">2017-01-10</time></div></div></div></div></header><main id="main" class="main"><div class="main-inner"><div class="content-wrap"><div id="content" class="content"><div id="posts" class="posts-expand"><article class="post post-type-normal" itemscope itemtype="http://schema.org/Article"><link itemprop="mainEntityOfPage" href="http://zhaozhanxu.com/2017/01/10/VPP/2017-01-10-VPP-Router2/"><span style="display:none" itemprop="author" itemscope itemtype="http://schema.org/Person"><meta itemprop="name" content="赵占旭"><meta itemprop="description" content=""><meta itemprop="image" content="/images/public/me.jpg"></span><span style="display:none" itemprop="publisher" itemscope itemtype="http://schema.org/Organization"><meta itemprop="name" content="赵占旭的博客"> <span style="display:none" itemprop="logo" itemscope itemtype="http://schema.org/ImageObject"><img style="display:none" itemprop="url image" alt="赵占旭的博客" src=""></span></span><div class="post-inner"><header class="post-header"><h2 class="post-title" itemprop="name headline"> [转]Cisco VPP 路由分析下</h2><div class="post-meta"><span class="post-time"><span class="post-meta-item-icon"><i class="fa fa-calendar-o"></i></span> <span class="post-meta-item-text">Posted on</span> <time title="Post created" itemprop="dateCreated datePublished" datetime="2017-01-10T00:00:00+08:00">2017-01-10</time></span></div></header><div class="post-info"><div class="post-categories"> <a class="color" href="/categories/VPP/" rel="tag">VPP</a></div><div class="post-tags"> <a class="color" href="/tags/DPDK/" rel="tag">DPDK</a> <a class="color" href="/tags/Network/" rel="tag">Network</a> <a class="color" href="/tags/VPP/" rel="tag">VPP</a></div><div class="clearfix"></div></div><div class="post-body" itemprop="articleBody"><p><strong>注：本文是转载，但不是100%的转载，可能稍微有些出入，原文地址<a href="http://blog.csdn.net/jqh9804/article/details/54310183" target="_blank" rel="noopener">点击这里</a></strong></p><a id="more"></a><h1 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h1><hr><p>VPP路由可以看作是思科iOS CEF的翻版。将路由分为路由表和转发表。路由表的实现基于hash，转发表的实现基于8-8-8-8 mtrie树。<br>路由表存储了所有可能的路由表项(其中最优路由将安装到转发表中)，转发表存储了实际使用的路由项(数据包转发真正查找的是这个转发表)。<br>VPP转发表查找的最后结果将得到一个DPO（data path object），DPO将指示数据包的下一步动作(分类，ARP查找，丢弃等等，请查看<code>DPO_TYPES</code>枚举类型)。</p><p>以下皆以ipv4来分析，只分析了我看懂了的一部分。</p><h2 id="路由表"><a href="#路由表" class="headerlink" title="路由表"></a>路由表</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">ip4_fib_t</span> &#123;</span></span><br><span class="line">    <span class="comment">//根据掩码大小对路由项作hash</span></span><br><span class="line">    uword *fib_entry_by_dst_address[<span class="number">33</span>];</span><br><span class="line"></span><br><span class="line">    <span class="comment">//8-8-8-8 mtrie转发表</span></span><br><span class="line">    <span class="keyword">ip4_fib_mtrie_t</span> mtrie;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Table ID (hash key) for this FIB.</span></span><br><span class="line">    u32 table_id;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Index into FIB vector. </span></span><br><span class="line">    u32 index;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// flow hash configuration</span></span><br><span class="line">    <span class="keyword">flow_hash_config_t</span> flow_hash_config;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// N-tuple classifier indices</span></span><br><span class="line">    u32 fwd_classify_table_index;</span><br><span class="line">    u32 rev_classify_table_index;</span><br><span class="line">&#125; <span class="keyword">ip4_fib_t</span>;</span><br></pre></td></tr></table></figure><p>路由表项hash链入fib_entry_by_dst_address中。<br>转发表项安装在mtrie中，这是实际被数据平面使用的查找数据库。<br>路由表的任何变化，将导致转发表的更新。</p><h2 id="路由表项"><a href="#路由表项" class="headerlink" title="路由表项"></a>路由表项</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">fib_entry_t_</span> &#123;</span></span><br><span class="line">    <span class="comment">//所有路由关键数据结构都已这个打头，可以看做是他们的基类。</span></span><br><span class="line">    <span class="comment">//用来将这些不同数据结构连在一起，又能用统一的接口来遍历。</span></span><br><span class="line">    <span class="keyword">fib_node_t</span> fe_node;</span><br><span class="line">    <span class="comment">//可以理解为路由目的地址+掩码</span></span><br><span class="line">    <span class="keyword">const</span> <span class="keyword">fib_prefix_t</span> fe_prefix;</span><br><span class="line">    <span class="comment">//The index of the FIB table this entry is in</span></span><br><span class="line">    u32 fe_fib_index;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * The load-balance used for forwarding.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * We don't share the EOS and non-EOS even in case when they could be</span></span><br><span class="line"><span class="comment">     * because:</span></span><br><span class="line"><span class="comment">     *   - complexity &amp; reliability v. memory</span></span><br><span class="line"><span class="comment">     *       determining the conditions where sharing is possible is non-trivial.</span></span><br><span class="line"><span class="comment">     *   - separate LBs means we can get the EOS bit right in the MPLS label DPO</span></span><br><span class="line"><span class="comment">     *     and so save a few clock cycles in the DP imposition node since we can</span></span><br><span class="line"><span class="comment">     *     paint the header straight on without the need to check the packet</span></span><br><span class="line"><span class="comment">     *     type to derive the EOS bit value.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">dpo_id_t</span> fe_lb; <span class="comment">// [FIB_FORW_CHAIN_MPLS_NUM];</span></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * Vector of source infos.</span></span><br><span class="line"><span class="comment">     * Most entries will only have 1 source. So we optimise for memory usage,</span></span><br><span class="line"><span class="comment">     * which is preferable since we have many entries.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 同一个路由目的，可以是由不同的来源添加的，</span></span><br><span class="line"><span class="comment">     * 所有来源类型查看fib_source_t_枚举类型，数值越小的来源，</span></span><br><span class="line"><span class="comment">     * 优先级越高，最高优先级的来源的路由将安装到转发表，</span></span><br><span class="line"><span class="comment">     * 低优先级来源的路由项默默地保存在最高优先级来源后面。</span></span><br><span class="line"><span class="comment">     * 这个数组是有序的，添加删除都将导致排序，0号位置为最优路由。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_entry_src_t</span> *fe_srcs;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * the path-list for which this entry is a child. This is also the path-list</span></span><br><span class="line"><span class="comment">     * that is contributing forwarding for this entry.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_node_index_t</span> fe_parent;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * index of this entry in the parent's child list.</span></span><br><span class="line"><span class="comment">     * This is set when this entry is added as a child, but can also</span></span><br><span class="line"><span class="comment">     * be changed by the parent as it manages its list.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    u32 fe_sibling;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//A vector of delegates.</span></span><br><span class="line">    <span class="keyword">fib_entry_delegate_t</span> *fe_delegates;</span><br><span class="line">&#125; <span class="keyword">fib_entry_t</span>;</span><br></pre></td></tr></table></figure><h2 id="source"><a href="#source" class="headerlink" title="source"></a>source</h2><p>表明该路由项的来源，每个source结构中包含了一个path_list，这个表包含了所有可能的下一跳。</p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">fib_entry_src_t_</span> &#123;</span></span><br><span class="line">    <span class="comment">// A vector of path extensions</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">fib_path_ext_t_</span> *<span class="title">fes_path_exts</span>;</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * The path-list created by the source</span></span><br><span class="line"><span class="comment">     * 通过它可以找到该source的path_list</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_node_index_t</span> fes_pl;</span><br><span class="line">    <span class="comment">// Which source this info block is for</span></span><br><span class="line">    <span class="keyword">fib_source_t</span> fes_src;</span><br><span class="line">    <span class="comment">// Flags on the source</span></span><br><span class="line">    <span class="keyword">fib_entry_src_flag_t</span> fes_flags;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * 1 bytes ref count. This is not the number of users of the Entry</span></span><br><span class="line"><span class="comment">     * (which is itself not large, due to path-list sharing), but the number</span></span><br><span class="line"><span class="comment">     * of times a given source has been added. Which is even fewer</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    u8 fes_ref_count;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Flags the source contributes to the entry</span></span><br><span class="line">    <span class="keyword">fib_entry_flag_t</span> fes_entry_flags;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Source specific info</span></span><br><span class="line">    <span class="keyword">union</span> &#123;</span><br><span class="line">        <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">            <span class="comment">// the index of the FIB entry that is the covering entry</span></span><br><span class="line">            <span class="keyword">fib_node_index_t</span> fesr_cover;</span><br><span class="line">            <span class="comment">// This source's index in the cover's list</span></span><br><span class="line">            u32 fesr_sibling;</span><br><span class="line">        &#125; rr;</span><br><span class="line">        <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">            <span class="comment">// the index of the FIB entry that is the covering entry</span></span><br><span class="line">            <span class="keyword">fib_node_index_t</span> fesa_cover;</span><br><span class="line">            <span class="comment">// This source's index in the cover's list</span></span><br><span class="line">            u32 fesa_sibling;</span><br><span class="line">        &#125; adj;</span><br><span class="line">        <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">            <span class="comment">// the index of the FIB entry that is the covering entry</span></span><br><span class="line">            <span class="keyword">fib_node_index_t</span> fesi_cover;</span><br><span class="line">            <span class="comment">// This source's index in the cover's list</span></span><br><span class="line">            u32 fesi_sibling;</span><br><span class="line">        &#125; interface;</span><br><span class="line">        <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">            <span class="comment">// This MPLS local label associated with the prefix.</span></span><br><span class="line">            <span class="keyword">mpls_label_t</span> fesm_label;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// the indicies of the LFIB entries created</span></span><br><span class="line">            <span class="keyword">fib_node_index_t</span> fesm_lfes[<span class="number">2</span>];</span><br><span class="line">        &#125; mpls;</span><br><span class="line">        <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">            <span class="comment">// The source FIB index.</span></span><br><span class="line">            <span class="keyword">fib_node_index_t</span> fesl_fib_index;</span><br><span class="line">        &#125; lisp;</span><br><span class="line">    &#125;;</span><br><span class="line">&#125; <span class="keyword">fib_entry_src_t</span>;</span><br></pre></td></tr></table></figure><h2 id="path-path-list"><a href="#path-path-list" class="headerlink" title="path path_list:"></a>path path_list:</h2><p>为了到达目的路由的下一跳称作path，所有可能的下一跳组合成path_list。</p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">fib_path_list_t_</span> &#123;</span></span><br><span class="line">    <span class="comment">// A path-list is a node in the FIB graph.</span></span><br><span class="line">    <span class="keyword">fib_node_t</span> fpl_node;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Flags on the path-list</span></span><br><span class="line">    <span class="keyword">fib_path_list_flags_t</span> fpl_flags;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * The next-hop protocol for the paths in this path list.</span></span><br><span class="line"><span class="comment">     * Note that fixing the proto here means we don't support a mix of</span></span><br><span class="line"><span class="comment">     * v4 and v6 paths. ho hum.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_protocol_t</span> fpl_nh_proto;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * Vector of paths indicies for all configured paths.</span></span><br><span class="line"><span class="comment">     * For shareable path-lists this list MUST not change.</span></span><br><span class="line"><span class="comment">     * path数组，记录了所有下一跳</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_node_index_t</span> *fpl_paths;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// the RPF list calculated for this path list</span></span><br><span class="line">    <span class="keyword">fib_node_index_t</span> fpl_urpf;</span><br><span class="line">&#125; <span class="keyword">fib_path_list_t</span>;</span><br></pre></td></tr></table></figure><h1 id="关键函数"><a href="#关键函数" class="headerlink" title="关键函数"></a>关键函数</h1><hr><h2 id="路由的添加"><a href="#路由的添加" class="headerlink" title="路由的添加"></a>路由的添加</h2><p>从<code>vnet_ip_route_cmd</code>函数入手，这是通过CLI添加路由的入口函数。从中找到路由添加关键函数<code>fib_table_entry_path_add2</code>。</p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">fib_node_index_t</span> fib_table_entry_path_add2 (u32 fib_index,</span><br><span class="line">            <span class="keyword">const</span> <span class="keyword">fib_prefix_t</span> *prefix,</span><br><span class="line">            <span class="keyword">fib_source_t</span> source,</span><br><span class="line">            <span class="keyword">fib_entry_flag_t</span> flags,</span><br><span class="line">            <span class="keyword">fib_route_path_t</span> *rpath)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">fib_node_index_t</span> fib_entry_index;</span><br><span class="line">    <span class="keyword">fib_table_t</span> *fib_table;</span><br><span class="line">    u32 ii;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//找到路由表</span></span><br><span class="line">    fib_table = fib_table_get(fib_index, prefix-&gt;fp_proto);</span><br><span class="line">    <span class="comment">//精确匹配到路由表项，注意不是最长匹配。</span></span><br><span class="line">    fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (ii = <span class="number">0</span>; ii &lt; vec_len(rpath); ii++)</span><br><span class="line">    &#123;</span><br><span class="line">        fib_table_route_path_fixup(prefix, &amp;rpath[ii]);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (FIB_NODE_INDEX_INVALID == fib_entry_index)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//创建路由表项，包括souces，path_list等，比较复杂，将详细分析。</span></span><br><span class="line">        fib_entry_index = fib_entry_create(fib_index, prefix,</span><br><span class="line">                    source, flags,</span><br><span class="line">                    rpath);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//路由表项链入hash表，很简单。</span></span><br><span class="line">        fib_table_entry_insert(fib_table, prefix, fib_entry_index);</span><br><span class="line">        fib_table-&gt;ft_src_route_counts[source]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> was_sourced;</span><br><span class="line"></span><br><span class="line">        was_sourced = fib_entry_is_sourced(fib_entry_index, source);</span><br><span class="line">        <span class="comment">//添加一个下一跳到路由表项，可能会新建source，也可能只是在现有source的path_list中增加一个path</span></span><br><span class="line">        fib_entry_path_add(fib_entry_index, source, flags, rpath);;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (was_sourced != fib_entry_is_sourced(fib_entry_index, source))</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="comment">//如果这个source是从无到有，更新下统计值</span></span><br><span class="line">            fib_table-&gt;ft_src_route_counts[source]++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (fib_entry_index);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="新建路由项，并插入mtrie树"><a href="#新建路由项，并插入mtrie树" class="headerlink" title="新建路由项，并插入mtrie树"></a>新建路由项，并插入mtrie树</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">fib_node_index_t</span> fib_entry_create (u32 fib_index,</span><br><span class="line">            <span class="keyword">const</span> <span class="keyword">fib_prefix_t</span> *prefix,</span><br><span class="line">            <span class="keyword">fib_source_t</span> source,</span><br><span class="line">            <span class="keyword">fib_entry_flag_t</span> flags,</span><br><span class="line">            <span class="keyword">const</span> <span class="keyword">fib_route_path_t</span> *paths)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">fib_node_index_t</span> fib_entry_index;</span><br><span class="line">    <span class="keyword">fib_entry_t</span> *fib_entry;</span><br><span class="line"></span><br><span class="line">    ASSERT(<span class="number">0</span> &lt; vec_len(paths));</span><br><span class="line"></span><br><span class="line">    <span class="comment">//简单的分配一个初始化了的路由表项，很简单。</span></span><br><span class="line">    fib_entry = fib_entry_alloc(fib_index, prefix, &amp;fib_entry_index);</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * since this is a new entry create, we don't need to check for winning</span></span><br><span class="line"><span class="comment">     * sources - there is only one.</span></span><br><span class="line"><span class="comment">     * 不同的source有不同的fesv_add函数。这里就是为了调用它。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    fib_entry = fib_entry_src_action_add(fib_entry, source, flags,</span><br><span class="line">                drop_dpo_get(</span><br><span class="line">                    fib_proto_to_dpo(</span><br><span class="line">                        fib_entry_get_proto(fib_entry))));</span><br><span class="line">    <span class="comment">//不同的source有不同的fesv_path_swap函数。这里就是为了调用它。                                             </span></span><br><span class="line">    fib_entry_src_action_path_swap(fib_entry,</span><br><span class="line">                source,</span><br><span class="line">                flags,</span><br><span class="line">                paths);</span><br><span class="line">    <span class="comment">// handle possible realloc's by refetching the pointer</span></span><br><span class="line">    fib_entry = fib_entry_get(fib_entry_index);</span><br><span class="line">    <span class="comment">//不同的source有不同的fesv_activate函数。这里就是为了调用它。</span></span><br><span class="line">    <span class="comment">//如果该source没有fesv_activate函数，则调用fib_entry_src_action_install</span></span><br><span class="line">    fib_entry_src_action_activate(fib_entry, source);</span><br><span class="line"></span><br><span class="line">    <span class="comment">//调用source的fesv_installed函数和fesv_fwd_update函数</span></span><br><span class="line">    fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (fib_entry_index);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">fib_entry_t</span> *fib_entry_src_action_add (<span class="keyword">fib_entry_t</span> *fib_entry,</span><br><span class="line">            <span class="keyword">fib_source_t</span> source,</span><br><span class="line">            <span class="keyword">fib_entry_flag_t</span> flags,</span><br><span class="line">            <span class="keyword">const</span> <span class="keyword">dpo_id_t</span> *dpo)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">fib_node_index_t</span> fib_entry_index;</span><br><span class="line">    <span class="keyword">fib_entry_src_t</span> *esrc;</span><br><span class="line"></span><br><span class="line">    esrc = fib_entry_src_find_or_create(fib_entry, source, <span class="literal">NULL</span>);</span><br><span class="line"></span><br><span class="line">    esrc-&gt;fes_ref_count++;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//对应source必须是从无到有。否则就直接返回了。</span></span><br><span class="line">    <span class="keyword">if</span> (<span class="number">1</span> != esrc-&gt;fes_ref_count)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">// we only want to add the source on the 0-&gt;1 transition</span></span><br><span class="line">        <span class="keyword">return</span> (fib_entry);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    esrc-&gt;fes_entry_flags = flags;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * save variable so we can recover from a fib_entry realloc.</span></span><br><span class="line"><span class="comment">     * 接下来的函数调用可能会导致fib_entry pool重新分配（扩张），所以只有索引号肯定是保证不变</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    fib_entry_index = fib_entry_get_index(fib_entry);</span><br><span class="line"></span><br><span class="line">    <span class="comment">//这个场景调用的是fib_entry_src_api_add</span></span><br><span class="line">    <span class="keyword">if</span> (<span class="literal">NULL</span> != fib_entry_src_vft[source].fesv_add)</span><br><span class="line">    &#123;</span><br><span class="line">        fib_entry_src_vft[source].fesv_add(esrc,</span><br><span class="line">                    fib_entry,</span><br><span class="line">                    flags,</span><br><span class="line">                    fib_entry_get_proto(fib_entry),</span><br><span class="line">                    dpo);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//路由表项pool可能重新分配了，所以这里通过索引重新获取下。</span></span><br><span class="line">    fib_entry = fib_entry_get(fib_entry_index);</span><br><span class="line"></span><br><span class="line">    esrc-&gt;fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//这个lock理解为引用计数，不是多线程中的互斥lock</span></span><br><span class="line">    fib_path_list_lock(esrc-&gt;fes_pl);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// the source owns a lock on the entry</span></span><br><span class="line">    fib_entry_lock(fib_entry_get_index(fib_entry));</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (fib_entry);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p><code>fib_entry_src_api_add--&gt;fib_path_list_create_special</code></p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">fib_node_index_t</span> fib_path_list_create_special (<span class="keyword">fib_protocol_t</span> nh_proto,</span><br><span class="line">            <span class="keyword">fib_path_list_flags_t</span> flags,</span><br><span class="line">            <span class="keyword">const</span> <span class="keyword">dpo_id_t</span> *dpo)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">fib_node_index_t</span> path_index, path_list_index;</span><br><span class="line">    <span class="keyword">fib_path_list_t</span> *path_list;</span><br><span class="line"></span><br><span class="line">    path_list = fib_path_list_alloc(&amp;path_list_index);</span><br><span class="line">    path_list-&gt;fpl_flags = flags;</span><br><span class="line">    path_list-&gt;fpl_nh_proto = nh_proto;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//创建path，这个场景里创建的是FIB_PATH_LIST_FLAG_NONE，drop dpo</span></span><br><span class="line">    path_index =</span><br><span class="line">        fib_path_create_special(path_list_index,</span><br><span class="line">                    path_list-&gt;fpl_nh_proto,</span><br><span class="line">                    fib_path_list_flags_2_path_flags(flags),</span><br><span class="line">                    dpo);</span><br><span class="line">    <span class="comment">//path加入path_list中</span></span><br><span class="line">    vec_add1(path_list-&gt;fpl_paths, path_index);</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * we don't share path-lists. we can do PIC on them so why bother.</span></span><br><span class="line"><span class="comment">     * 最重要的部分，分析path_list中的path，生成path-&gt;fp_dpo。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    path_list = fib_path_list_resolve(path_list);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (path_list_index);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">fib_node_index_t</span> fib_path_create_special (<span class="keyword">fib_node_index_t</span> pl_index,</span><br><span class="line">            <span class="keyword">fib_protocol_t</span> nh_proto,</span><br><span class="line">            <span class="keyword">fib_path_cfg_flags_t</span> flags,</span><br><span class="line">            <span class="keyword">const</span> <span class="keyword">dpo_id_t</span> *dpo)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">fib_path_t</span> *path;</span><br><span class="line"></span><br><span class="line">    pool_get(fib_path_pool, path);</span><br><span class="line">    <span class="built_in">memset</span>(path, <span class="number">0</span>, <span class="keyword">sizeof</span>(*path));</span><br><span class="line"></span><br><span class="line">    fib_node_init(&amp;path-&gt;fp_node,</span><br><span class="line">                FIB_NODE_TYPE_PATH);</span><br><span class="line">    dpo_reset(&amp;path-&gt;fp_dpo);</span><br><span class="line"></span><br><span class="line">    path-&gt;fp_pl_index = pl_index;</span><br><span class="line">    path-&gt;fp_weight = <span class="number">1</span>;</span><br><span class="line">    path-&gt;fp_nh_proto = nh_proto;</span><br><span class="line">    path-&gt;fp_via_fib = FIB_NODE_INDEX_INVALID;</span><br><span class="line">    path-&gt;fp_cfg_flags = flags;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (FIB_PATH_CFG_FLAG_DROP &amp; flags)</span><br><span class="line">    &#123;</span><br><span class="line">        path-&gt;fp_type = FIB_PATH_TYPE_SPECIAL;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (FIB_PATH_CFG_FLAG_LOCAL &amp; flags)</span><br><span class="line">    &#123;</span><br><span class="line">        path-&gt;fp_type = FIB_PATH_TYPE_RECEIVE;</span><br><span class="line">        path-&gt;attached.fp_interface = FIB_NODE_INDEX_INVALID;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//本场景使用的是这里</span></span><br><span class="line">        path-&gt;fp_type = FIB_PATH_TYPE_EXCLUSIVE;</span><br><span class="line">        ASSERT(<span class="literal">NULL</span> != dpo);</span><br><span class="line">        dpo_copy(&amp;path-&gt;exclusive.fp_ex_dpo, dpo);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (fib_path_get_index(path));</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">static</span> fib_path_list_t *<span class="title">fib_path_list_resolve</span> <span class="params">(<span class="keyword">fib_path_list_t</span> *path_list)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">fib_node_index_t</span> *path_index, *paths, path_list_index;</span><br><span class="line"></span><br><span class="line">    ASSERT(!(path_list-&gt;fpl_flags &amp; FIB_PATH_LIST_FLAG_RESOLVED));</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * resolving a path-list is a recursive action. this means more path</span></span><br><span class="line"><span class="comment">     * lists can be created during this call, and hence this path-list</span></span><br><span class="line"><span class="comment">     * can be realloc'd. so we work with copies.</span></span><br><span class="line"><span class="comment">     * this function is called only once per-path list, so its no great overhead.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    path_list_index = fib_path_list_get_index(path_list);</span><br><span class="line">    paths = vec_dup(path_list-&gt;fpl_paths);</span><br><span class="line"></span><br><span class="line">    vec_foreach (path_index, paths)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//FIB_PATH_TYPE_RECURSIVE类型的path会导致递归调用，可能导致path_list pool重分配。</span></span><br><span class="line">        fib_path_resolve(*path_index);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    vec_free(paths);</span><br><span class="line">    path_list = fib_path_list_get(path_list_index);</span><br><span class="line"></span><br><span class="line">    FIB_PATH_LIST_DBG(path_list, <span class="string">"resovled"</span>);</span><br><span class="line">    fib_path_list_mk_urpf(path_list);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (path_list);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//本函数最终目的是为path分析出DPO，保存到path-&gt;fp_dpo成员中，细节太多，博主已晕，以后再补</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">fib_path_resolve</span> <span class="params">(<span class="keyword">fib_node_index_t</span> path_index)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">fib_path_t</span> *path;</span><br><span class="line"></span><br><span class="line">    path = fib_path_get(path_index);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// hope for the best.</span></span><br><span class="line">    path-&gt;fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// the forced drop path resolves via the drop adj</span></span><br><span class="line">    <span class="keyword">if</span> (fib_path_is_permanent_drop(path))</span><br><span class="line">    &#123;</span><br><span class="line">        dpo_copy(&amp;path-&gt;fp_dpo,</span><br><span class="line">                    drop_dpo_get(fib_proto_to_dpo(path-&gt;fp_nh_proto)));</span><br><span class="line">        path-&gt;fp_oper_flags &amp;= ~FIB_PATH_OPER_FLAG_RESOLVED;</span><br><span class="line">        <span class="keyword">return</span> (fib_path_is_resolved(path_index));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">switch</span> (path-&gt;fp_type)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">case</span> FIB_PATH_TYPE_ATTACHED_NEXT_HOP:</span><br><span class="line">            fib_path_attached_next_hop_set(path);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> FIB_PATH_TYPE_ATTACHED:</span><br><span class="line">            <span class="comment">// path-&gt;attached.fp_interface</span></span><br><span class="line">            <span class="keyword">if</span> (!vnet_sw_interface_is_admin_up(vnet_get_main(),</span><br><span class="line">                            path-&gt;attached.fp_interface))</span><br><span class="line">            &#123;</span><br><span class="line">                path-&gt;fp_oper_flags &amp;= ~FIB_PATH_OPER_FLAG_RESOLVED;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (vnet_sw_interface_is_p2p(vnet_get_main(),</span><br><span class="line">                            path-&gt;attached.fp_interface))</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="comment">/*</span></span><br><span class="line"><span class="comment">                 * point-2-point interfaces do not require a glean, since</span></span><br><span class="line"><span class="comment">                 * there is nothing to ARP. Install a rewrite/nbr adj instead</span></span><br><span class="line"><span class="comment">                 */</span></span><br><span class="line">                dpo_set(&amp;path-&gt;fp_dpo,</span><br><span class="line">                            DPO_ADJACENCY,</span><br><span class="line">                            fib_proto_to_dpo(path-&gt;fp_nh_proto),</span><br><span class="line">                            adj_nbr_add_or_lock(</span><br><span class="line">                                path-&gt;fp_nh_proto,</span><br><span class="line">                                fib_proto_to_link(path-&gt;fp_nh_proto),</span><br><span class="line">                                &amp;zero_addr,</span><br><span class="line">                                path-&gt;attached.fp_interface));</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">            &#123;</span><br><span class="line">                dpo_set(&amp;path-&gt;fp_dpo,</span><br><span class="line">                            DPO_ADJACENCY_GLEAN,</span><br><span class="line">                            fib_proto_to_dpo(path-&gt;fp_nh_proto),</span><br><span class="line">                            adj_glean_add_or_lock(path-&gt;fp_nh_proto,</span><br><span class="line">                                path-&gt;attached.fp_interface,</span><br><span class="line">                                <span class="literal">NULL</span>));</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">/*</span></span><br><span class="line"><span class="comment">             * become a child of the adjacency so we receive updates</span></span><br><span class="line"><span class="comment">             * when the interface state changes</span></span><br><span class="line"><span class="comment">             */</span></span><br><span class="line">            path-&gt;fp_sibling = adj_child_add(path-&gt;fp_dpo.dpoi_index,</span><br><span class="line">                        FIB_NODE_TYPE_PATH,</span><br><span class="line">                        fib_path_get_index(path));</span><br><span class="line"></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> FIB_PATH_TYPE_RECURSIVE:</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="comment">/*</span></span><br><span class="line"><span class="comment">                 * Create a RR source entry in the table for the address</span></span><br><span class="line"><span class="comment">                 * that this path recurses through.</span></span><br><span class="line"><span class="comment">                 * This resolve action is recursive, hence we may create</span></span><br><span class="line"><span class="comment">                 * more paths in the process. more creates mean maybe realloc</span></span><br><span class="line"><span class="comment">                 * of this path.</span></span><br><span class="line"><span class="comment">                 */</span></span><br><span class="line">                <span class="keyword">fib_node_index_t</span> fei;</span><br><span class="line">                <span class="keyword">fib_prefix_t</span> pfx;</span><br><span class="line"></span><br><span class="line">                ASSERT(FIB_NODE_INDEX_INVALID == path-&gt;fp_via_fib);</span><br><span class="line"></span><br><span class="line">                <span class="keyword">if</span> (FIB_PROTOCOL_MPLS == path-&gt;fp_nh_proto)</span><br><span class="line">                &#123;</span><br><span class="line">                    fib_prefix_from_mpls_label(path-&gt;recursive.fp_nh.fp_local_label, &amp;pfx);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                &#123;</span><br><span class="line">                    fib_prefix_from_ip46_addr(&amp;path-&gt;recursive.fp_nh.fp_ip, &amp;pfx);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                <span class="comment">//把下一跳也插入路由表，开始递归了</span></span><br><span class="line">                fei = fib_table_entry_special_add(path-&gt;recursive.fp_tbl_id,</span><br><span class="line">                            &amp;pfx,</span><br><span class="line">                            FIB_SOURCE_RR,</span><br><span class="line">                            FIB_ENTRY_FLAG_NONE,</span><br><span class="line">                            ADJ_INDEX_INVALID);</span><br><span class="line"></span><br><span class="line">                path = fib_path_get(path_index);</span><br><span class="line">                path-&gt;fp_via_fib = fei;</span><br><span class="line"></span><br><span class="line">                <span class="comment">/*</span></span><br><span class="line"><span class="comment">                 * become a dependent child of the entry so the path is </span></span><br><span class="line"><span class="comment">                 * informed when the forwarding for the entry changes.</span></span><br><span class="line"><span class="comment">                 */</span></span><br><span class="line">                path-&gt;fp_sibling = fib_entry_child_add(path-&gt;fp_via_fib,</span><br><span class="line">                            FIB_NODE_TYPE_PATH,</span><br><span class="line">                            fib_path_get_index(path));</span><br><span class="line"></span><br><span class="line">                <span class="comment">// create and configure the IP DPO</span></span><br><span class="line">                fib_path_recursive_adj_update(</span><br><span class="line">                            path,</span><br><span class="line">                            fib_path_proto_to_chain_type(path-&gt;fp_nh_proto),</span><br><span class="line">                            &amp;path-&gt;fp_dpo);</span><br><span class="line"></span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        <span class="keyword">case</span> FIB_PATH_TYPE_SPECIAL:</span><br><span class="line">            <span class="comment">// Resolve via the drop</span></span><br><span class="line">            dpo_copy(&amp;path-&gt;fp_dpo,</span><br><span class="line">                        drop_dpo_get(fib_proto_to_dpo(path-&gt;fp_nh_proto)));</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> FIB_PATH_TYPE_DEAG:</span><br><span class="line">            <span class="comment">/*</span></span><br><span class="line"><span class="comment">             * Resolve via a lookup DPO.</span></span><br><span class="line"><span class="comment">             * FIXME. control plane should add routes with a table ID</span></span><br><span class="line"><span class="comment">             */</span></span><br><span class="line">            lookup_dpo_add_or_lock_w_fib_index(path-&gt;deag.fp_tbl_id,</span><br><span class="line">                        fib_proto_to_dpo(path-&gt;fp_nh_proto),</span><br><span class="line">                        LOOKUP_INPUT_DST_ADDR,</span><br><span class="line">                        LOOKUP_TABLE_FROM_CONFIG,</span><br><span class="line">                        &amp;path-&gt;fp_dpo);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> FIB_PATH_TYPE_RECEIVE:</span><br><span class="line">            <span class="comment">// Resolve via a receive DPO.</span></span><br><span class="line">            receive_dpo_add_or_lock(fib_proto_to_dpo(path-&gt;fp_nh_proto),</span><br><span class="line">                        path-&gt;receive.fp_interface,</span><br><span class="line">                        &amp;path-&gt;receive.fp_addr,</span><br><span class="line">                        &amp;path-&gt;fp_dpo);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> FIB_PATH_TYPE_EXCLUSIVE:</span><br><span class="line">            <span class="comment">// Resolve via the user provided DPO</span></span><br><span class="line">            dpo_copy(&amp;path-&gt;fp_dpo, &amp;path-&gt;exclusive.fp_ex_dpo);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (fib_path_is_resolved(path_index));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">void</span> <span class="title">fib_entry_src_api_path_swap</span> <span class="params">(<span class="keyword">fib_entry_src_t</span> *src,</span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">const</span> <span class="keyword">fib_entry_t</span> *entry,</span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">fib_path_list_flags_t</span> pl_flags,</span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">const</span> <span class="keyword">fib_route_path_t</span> *paths)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//这里是为了减少path_list重复，看看hash表里有没有一样的path_list，没有就加进hash表里</span></span><br><span class="line">    src-&gt;fes_pl = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED | pl_flags),</span><br><span class="line">                       paths);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">fib_node_index_t</span> fib_path_list_create (<span class="keyword">fib_path_list_flags_t</span> flags,</span><br><span class="line">              <span class="keyword">const</span> <span class="keyword">fib_route_path_t</span> *rpaths)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">fib_node_index_t</span> path_list_index, old_path_list_index;</span><br><span class="line">    <span class="keyword">fib_path_list_t</span> *path_list;</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line"></span><br><span class="line">    flags = fib_path_list_flags_fixup(flags);</span><br><span class="line">    path_list = fib_path_list_alloc(&amp;path_list_index);</span><br><span class="line">    path_list-&gt;fpl_flags = flags;</span><br><span class="line">    <span class="comment">// we'll assume for now all paths are the same next-hop protocol</span></span><br><span class="line">    path_list-&gt;fpl_nh_proto = rpaths[<span class="number">0</span>].frp_proto;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//创建path_list中的所有path</span></span><br><span class="line">    vec_foreach_index(i, rpaths)</span><br><span class="line">    &#123;</span><br><span class="line">    vec_add1(path_list-&gt;fpl_paths,</span><br><span class="line">         fib_path_create(path_list_index,</span><br><span class="line">                 path_list-&gt;fpl_nh_proto,</span><br><span class="line">                 fib_path_list_flags_2_path_flags(flags),</span><br><span class="line">                 &amp;rpaths[i]));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// If a shared path list is requested, consult the DB for a match</span></span><br><span class="line">    <span class="keyword">if</span> (flags &amp; FIB_PATH_LIST_FLAG_SHARED)</span><br><span class="line">    &#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * check for a matching path-list in the DB.</span></span><br><span class="line"><span class="comment">     * If we find one then we can return the existing one and destroy the</span></span><br><span class="line"><span class="comment">     * new one just created.</span></span><br><span class="line"><span class="comment">     * fib_path_list_db_hash_key_equal。</span></span><br><span class="line"><span class="comment">     * 可以知道，key其实是把path_list中每一个path的部分内容，</span></span><br><span class="line"><span class="comment">     * 累积成    key，可以无脑理解为就是确保两个path_list中每个path内容一样，</span></span><br><span class="line"><span class="comment">     * 才能认为这两个path_list相等。*/</span></span><br><span class="line">    old_path_list_index = fib_path_list_db_find(path_list);</span><br><span class="line">    <span class="keyword">if</span> (FIB_NODE_INDEX_INVALID != old_path_list_index)</span><br><span class="line">    &#123;</span><br><span class="line">        fib_path_list_destroy(path_list);</span><br><span class="line"></span><br><span class="line">        path_list_index = old_path_list_index;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">         * if there was not a matching path-list, then this</span></span><br><span class="line"><span class="comment">         * new one will need inserting into the DB and resolving.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        fib_path_list_db_insert(path_list_index);</span><br><span class="line">        path_list = fib_path_list_resolve(path_list);</span><br><span class="line">    &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * no shared path list requested. resolve and use the one</span></span><br><span class="line"><span class="comment">     * just created.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    path_list = fib_path_list_resolve(path_list);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (path_list_index);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="转发表安装"><a href="#转发表安装" class="headerlink" title="转发表安装"></a>转发表安装</h2><p>路由表，路由表项，source，path_list，path都准备好了。接下来要安装到转发表中了，安装后才是真正对数据包转发<br>生效</p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">fib_entry_src_action_activate</span> <span class="params">(<span class="keyword">fib_entry_t</span> *fib_entry,</span></span></span><br><span class="line"><span class="function"><span class="params">            <span class="keyword">fib_source_t</span> source)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> houston_we_are_go_for_install;</span><br><span class="line">    <span class="keyword">fib_entry_src_t</span> *esrc;</span><br><span class="line"></span><br><span class="line">    esrc = fib_entry_src_find(fib_entry, source, <span class="literal">NULL</span>);</span><br><span class="line"></span><br><span class="line">    ASSERT(!(esrc-&gt;fes_flags &amp; FIB_ENTRY_SRC_FLAG_ACTIVE));</span><br><span class="line">    ASSERT(esrc-&gt;fes_flags &amp; FIB_ENTRY_SRC_FLAG_ADDED);</span><br><span class="line"></span><br><span class="line">    esrc-&gt;fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (<span class="literal">NULL</span> != fib_entry_src_vft[source].fesv_activate)</span><br><span class="line">    &#123;</span><br><span class="line">        houston_we_are_go_for_install =</span><br><span class="line">            fib_entry_src_vft[source].fesv_activate(esrc, fib_entry);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">         * the source is not providing an activate function, we'll assume</span></span><br><span class="line"><span class="comment">         * therefore it has no objection to installing the entry</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        houston_we_are_go_for_install = !<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * link to the path-list provided by the source, and go check</span></span><br><span class="line"><span class="comment">     * if that forms any loops in the graph.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    fib_entry-&gt;fe_parent = esrc-&gt;fes_pl;</span><br><span class="line">    fib_entry-&gt;fe_sibling =</span><br><span class="line">        fib_path_list_child_add(fib_entry-&gt;fe_parent,</span><br><span class="line">                    FIB_NODE_TYPE_ENTRY,</span><br><span class="line">                    fib_entry_get_index(fib_entry));</span><br><span class="line"></span><br><span class="line">    fib_entry_recursive_loop_detect_i(fib_entry-&gt;fe_parent);</span><br><span class="line"></span><br><span class="line">    FIB_ENTRY_DBG(fib_entry, <span class="string">"activate: %d"</span>,</span><br><span class="line">                fib_entry-&gt;fe_parent);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (<span class="number">0</span> != houston_we_are_go_for_install)</span><br><span class="line">    &#123;</span><br><span class="line">        fib_entry_src_action_install(fib_entry, source);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        fib_entry_src_action_uninstall(fib_entry);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">fib_entry_src_action_install</span> <span class="params">(<span class="keyword">fib_entry_t</span> *fib_entry,</span></span></span><br><span class="line"><span class="function"><span class="params">            <span class="keyword">fib_source_t</span> source)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * Install the forwarding chain for the given source into the forwarding</span></span><br><span class="line"><span class="comment">     * tables</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_forward_chain_type_t</span> fct;</span><br><span class="line">    <span class="keyword">fib_entry_src_t</span> *esrc;</span><br><span class="line">    <span class="keyword">int</span> insert;</span><br><span class="line"></span><br><span class="line">    fct = fib_entry_get_default_chain_type(fib_entry);</span><br><span class="line">    esrc = fib_entry_src_find(fib_entry, source, <span class="literal">NULL</span>);</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * Every entry has its own load-balance object. All changes to the entry's</span></span><br><span class="line"><span class="comment">     * forwarding result in an inplace modify of the load-balance. This means</span></span><br><span class="line"><span class="comment">     * the load-balance object only needs to be added to the forwarding</span></span><br><span class="line"><span class="comment">     * DB once, when it is created.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    insert = !dpo_id_is_valid(&amp;fib_entry-&gt;fe_lb);</span><br><span class="line"></span><br><span class="line">    <span class="comment">//准备转发表中的最终DPO。利用上文提到的path-&gt;fp_dpo，来构建最终DPO</span></span><br><span class="line">    fib_entry_src_mk_lb(fib_entry, esrc, fct, &amp;fib_entry-&gt;fe_lb);</span><br><span class="line"></span><br><span class="line">    ASSERT(dpo_id_is_valid(&amp;fib_entry-&gt;fe_lb));</span><br><span class="line">    FIB_ENTRY_DBG(fib_entry, <span class="string">"install: %d"</span>, fib_entry-&gt;fe_lb);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// insert the adj into the data-plane forwarding trie</span></span><br><span class="line">    <span class="keyword">if</span> (insert)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//安装到8-8-8-8 mtrie转发表</span></span><br><span class="line">        fib_table_fwding_dpo_update(fib_entry-&gt;fe_fib_index,</span><br><span class="line">                    &amp;fib_entry-&gt;fe_prefix,</span><br><span class="line">                    &amp;fib_entry-&gt;fe_lb);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * if any of the other chain types are already created they will need</span></span><br><span class="line"><span class="comment">     * updating too</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_entry_delegate_type_t</span> fdt;</span><br><span class="line">    <span class="keyword">fib_entry_delegate_t</span> *fed;</span><br><span class="line"></span><br><span class="line">    FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,</span><br><span class="line">                &#123;</span><br><span class="line">                fib_entry_src_mk_lb(fib_entry, esrc,</span><br><span class="line">                            fib_entry_delegate_type_to_chain_type(fdt),</span><br><span class="line">                            &amp;fed-&gt;fd_dpo);</span><br><span class="line">                &#125;);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">fib_entry_src_mk_lb</span> <span class="params">(<span class="keyword">fib_entry_t</span> *fib_entry,</span></span></span><br><span class="line"><span class="function"><span class="params">            <span class="keyword">const</span> <span class="keyword">fib_entry_src_t</span> *esrc,</span></span></span><br><span class="line"><span class="function"><span class="params">            <span class="keyword">fib_forward_chain_type_t</span> fct,</span></span></span><br><span class="line"><span class="function"><span class="params">            <span class="keyword">dpo_id_t</span> *dpo_lb)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">dpo_proto_t</span> lb_proto;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * If the entry has path extensions then we construct a load-balance</span></span><br><span class="line"><span class="comment">     * by stacking the extensions on the forwarding chains of the paths.</span></span><br><span class="line"><span class="comment">     * Otherwise we use the load-balance of the path-list</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">fib_entry_src_collect_forwarding_ctx_t</span> ctx = &#123;</span><br><span class="line">        .esrc = esrc,</span><br><span class="line">        .fib_entry = fib_entry,</span><br><span class="line">        .next_hops = <span class="literal">NULL</span>,</span><br><span class="line">        .is_recursive = <span class="number">0</span>,</span><br><span class="line">        .fct = fct,</span><br><span class="line">    &#125;;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * As an optimisation we allocate the vector of next-hops to be sized</span></span><br><span class="line"><span class="comment">     * equal to the maximum nuber of paths we will need, which is also the</span></span><br><span class="line"><span class="comment">     * most likely number we will need, since in most cases the paths are 'up'.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    vec_validate(ctx.next_hops, fib_path_list_get_n_paths(esrc-&gt;fes_pl));</span><br><span class="line">    vec_reset_length(ctx.next_hops);</span><br><span class="line"></span><br><span class="line">    lb_proto = fib_proto_to_dpo(fib_entry-&gt;fe_prefix.fp_proto);</span><br><span class="line"></span><br><span class="line">    fib_path_list_walk(esrc-&gt;fes_pl,</span><br><span class="line">                fib_entry_src_collect_forwarding,</span><br><span class="line">                &amp;ctx);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (esrc-&gt;fes_entry_flags &amp; FIB_ENTRY_FLAG_EXCLUSIVE)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">         * the client provided the DPO that the entry should link to.</span></span><br><span class="line"><span class="comment">         * all entries must link to a LB, so if it is an LB already</span></span><br><span class="line"><span class="comment">         * then we can use it.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="keyword">if</span> ((<span class="number">1</span> == vec_len(ctx.next_hops)) &amp;&amp;</span><br><span class="line">                    (DPO_LOAD_BALANCE == ctx.next_hops[<span class="number">0</span>].path_dpo.dpoi_type))</span><br><span class="line">        &#123;</span><br><span class="line">            dpo_copy(dpo_lb, &amp;ctx.next_hops[<span class="number">0</span>].path_dpo);</span><br><span class="line">            dpo_reset(&amp;ctx.next_hops[<span class="number">0</span>].path_dpo);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (!dpo_id_is_valid(dpo_lb))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">// first time create</span></span><br><span class="line">        <span class="keyword">flow_hash_config_t</span> fhc;</span><br><span class="line"></span><br><span class="line">        fhc = fib_table_get_flow_hash_config(fib_entry-&gt;fe_fib_index,</span><br><span class="line">                    dpo_proto_to_fib(lb_proto));</span><br><span class="line">        dpo_set(dpo_lb,</span><br><span class="line">                    DPO_LOAD_BALANCE,</span><br><span class="line">                    lb_proto,</span><br><span class="line">                    load_balance_create(<span class="number">0</span>, lb_proto, fhc));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    load_balance_multipath_update(dpo_lb,</span><br><span class="line">                ctx.next_hops,</span><br><span class="line">                fib_entry_calc_lb_flags(&amp;ctx));</span><br><span class="line">    vec_free(ctx.next_hops);</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * if this entry is sourced by the uRPF-exempt source then we</span></span><br><span class="line"><span class="comment">     * append the always present local0 interface (index 0) to the</span></span><br><span class="line"><span class="comment">     * uRPF list so it is not empty. that way packets pass the loose check.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">index_t</span> ui = fib_path_list_get_urpf(esrc-&gt;fes_pl);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (fib_entry_is_sourced(fib_entry_get_index(fib_entry),</span><br><span class="line">                    FIB_SOURCE_URPF_EXEMPT) &amp;&amp;</span><br><span class="line">                (<span class="number">0</span> == fib_urpf_check_size(ui)))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">         * The uRPF list we get from the path-list is shared by all</span></span><br><span class="line"><span class="comment">         * other users of the list, but the uRPF exemption applies</span></span><br><span class="line"><span class="comment">         * only to this prefix. So we need our own list.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        ui = fib_urpf_list_alloc_and_lock();</span><br><span class="line">        fib_urpf_list_append(ui, <span class="number">0</span>);</span><br><span class="line">        fib_urpf_list_bake(ui);</span><br><span class="line">        load_balance_set_urpf(dpo_lb-&gt;dpoi_index, ui);</span><br><span class="line">        fib_urpf_list_unlock(ui);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        load_balance_set_urpf(dpo_lb-&gt;dpoi_index, ui);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></div><div></div><footer class="post-footer"><div class="post-nav"><div class="post-nav-next post-nav-item"><a href="/2016/12/19/VPP/2016-12-19-VPP-Router1/" rel="next" title="[转]Cisco VPP 路由分析上"><i class="fa fa-chevron-left"></i> [转]Cisco VPP 路由分析上</a></div><div class="post-nav-prev post-nav-item"> <a href="/2017/01/29/VPP/2017-01-29-VPP-Feature/" rel="prev" title="[转]Cisco VPP Feature机制">[转]Cisco VPP Feature机制<i class="fa fa-chevron-right"></i></a></div></div></footer></div></article><div class="post-copyright"><p><span>注意:</span>所有文章非特别说明皆为原创。为保证信息与源同步，转载时请务必注明文章出处！谢谢合作 :-)</p><p> <span>原始链接:</span><a class="post-url" href="/2017/01/10/VPP/2017-01-10-VPP-Router2/" title="[转]Cisco VPP 路由分析下">http://zhaozhanxu.com/2017/01/10/VPP/2017-01-10-VPP-Router2/</a><span class="copy-path" data-clipboard-text="原文: http://zhaozhanxu.com/2017/01/10/VPP/2017-01-10-VPP-Router2/　　作者: 赵占旭" title="点击复制文章链接"><i class="fa fa-clipboard"></i></span><script src="/js/clipboard.min.js"></script><script>var clipboard=new Clipboard(".copy-path")</script></p><p> <span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/cn" title="中国大陆 (CC BY-NC-SA 4.0 CN)" target="_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。</p></div></div></div><div class="comments" id="comments"></div></div><div class="sidebar-toggle"><div class="sidebar-toggle-line-wrap"><span class="sidebar-toggle-line sidebar-toggle-line-first"></span><span class="sidebar-toggle-line sidebar-toggle-line-middle"></span><span class="sidebar-toggle-line sidebar-toggle-line-last"></span></div></div><aside id="sidebar" class="sidebar"><div class="sidebar-inner"><ul class="sidebar-nav motion-element"><li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap"> Table of Contents</li><li class="sidebar-nav-overview" data-target="site-overview"> Overview</li></ul><section class="site-overview sidebar-panel"><div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person"> <a href="/about"><img class="site-author-image" itemprop="image" src="/images/public/me.jpg" alt="赵占旭"><p class="site-author-name" itemprop="name">赵占旭</p><p class="site-description motion-element" itemprop="description"></p></a></div><nav class="site-state motion-element"><div class="site-state-item site-state-posts"> <a href="/archives"><span class="site-state-item-count">61</span> <span class="site-state-item-name">posts</span></a></div><div class="site-state-item site-state-categories"> <a href="/categories"><span class="site-state-item-count">7</span> <span class="site-state-item-name">categories</span></a></div><div class="site-state-item site-state-tags"> <a href="/tags"><span class="site-state-item-count">14</span> <span class="site-state-item-name">tags</span></a></div></nav><div class="feed-link motion-element"><a href="/atom.xml" rel="alternate"><i class="fa fa-rss"></i> RSS</a></div><div class="links-of-author motion-element"><span class="links-of-author-item"><a href="mailto:zhaozhanxu@163.com" target="_blank" title="Mail"><i class="fa fa-fw fa-envelope"></i> Mail</a></span><span class="links-of-author-item"><a href="https://github.com/zhaozhanxu" target="_blank" title="GitHub"><i class="fa fa-fw fa-github"></i> GitHub</a></span><span class="links-of-author-item"><a href="https://www.linkedin.com/in/zhaozhanxu" target="_blank" title="LinkedIn"><i class="fa fa-fw fa-linkedin"></i> LinkedIn</a></span><span class="links-of-author-item"><a href="https://twitter.com/zhaozhanxu" target="_blank" title="Twitter"><i class="fa fa-fw fa-twitter"></i> Twitter</a></span><span class="links-of-author-item"><a href="/about/" target="_blank" title="Wechat"><i class="fa fa-fw fa-wechat"></i> Wechat</a></span><span class="links-of-author-item"><a href="/about/" target="_blank" title="QQ"><i class="fa fa-fw fa-qq"></i> QQ</a></span></div><div class="links-of-blogroll motion-element links-of-blogroll-inline"><div class="links-of-blogroll-title"><i class="fa fa-fw fa-address-book"></i> 基情链接</div><ul class="links-of-blogroll-list"><li class="links-of-blogroll-item"> <a href="http://blog.csdn.net/jqh9804" title="呆子辉" target="_blank">呆子辉</a></li></ul></div></section><section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active"><div class="post-toc"><div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#基本概念"><span class="nav-number">1.</span><span class="nav-text"><a href="#&#x57FA;&#x672C;&#x6982;&#x5FF5;" class="headerlink" title="&#x57FA;&#x672C;&#x6982;&#x5FF5;"></a> &#x57FA;&#x672C;&#x6982;&#x5FF5;</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#路由表"><span class="nav-number">1.1.</span><span class="nav-text"><a href="#&#x8DEF;&#x7531;&#x8868;" class="headerlink" title="&#x8DEF;&#x7531;&#x8868;"></a> &#x8DEF;&#x7531;&#x8868;</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#路由表项"><span class="nav-number">1.2.</span><span class="nav-text"><a href="#&#x8DEF;&#x7531;&#x8868;&#x9879;" class="headerlink" title="&#x8DEF;&#x7531;&#x8868;&#x9879;"></a> &#x8DEF;&#x7531;&#x8868;&#x9879;</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#source"><span class="nav-number">1.3.</span><span class="nav-text"><a href="#source" class="headerlink" title="source"></a> source</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#path-path-list"><span class="nav-number">1.4.</span><span class="nav-text"><a href="#path-path-list" class="headerlink" title="path path_list:"></a> path path_list:</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#关键函数"><span class="nav-number">2.</span><span class="nav-text"><a href="#&#x5173;&#x952E;&#x51FD;&#x6570;" class="headerlink" title="&#x5173;&#x952E;&#x51FD;&#x6570;"></a> &#x5173;&#x952E;&#x51FD;&#x6570;</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#路由的添加"><span class="nav-number">2.1.</span><span class="nav-text"><a href="#&#x8DEF;&#x7531;&#x7684;&#x6DFB;&#x52A0;" class="headerlink" title="&#x8DEF;&#x7531;&#x7684;&#x6DFB;&#x52A0;"></a> &#x8DEF;&#x7531;&#x7684;&#x6DFB;&#x52A0;</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#新建路由项，并插入mtrie树"><span class="nav-number">2.2.</span><span class="nav-text"><a href="#&#x65B0;&#x5EFA;&#x8DEF;&#x7531;&#x9879;&#xFF0C;&#x5E76;&#x63D2;&#x5165;mtrie&#x6811;" class="headerlink" title="&#x65B0;&#x5EFA;&#x8DEF;&#x7531;&#x9879;&#xFF0C;&#x5E76;&#x63D2;&#x5165;mtrie&#x6811;"></a> &#x65B0;&#x5EFA;&#x8DEF;&#x7531;&#x9879;&#xFF0C;&#x5E76;&#x63D2;&#x5165;mtrie&#x6811;</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#转发表安装"><span class="nav-number">2.3.</span><span class="nav-text"><a href="#&#x8F6C;&#x53D1;&#x8868;&#x5B89;&#x88C5;" class="headerlink" title="&#x8F6C;&#x53D1;&#x8868;&#x5B89;&#x88C5;"></a> &#x8F6C;&#x53D1;&#x8868;&#x5B89;&#x88C5;</span></a></li></ol></li></ol></div></div></section></div></aside></div></main><footer id="footer" class="footer"><div class="footer-inner"><div class="copyright"> &copy; 2016 - <span itemprop="copyrightYear">2017</span><span class="with-love"><i class="fa fa-heart"></i></span> <span class="author" itemprop="copyrightHolder">赵占旭</span></div><div class="powered-by"> Powered by <a class="theme-link" href="https://hexo.io">Hexo</a></div><div class="theme-info"> Theme - <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">NexT</a></div><div class="busuanzi-count"><script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script><span class="site-uv"><i class="fa fa-user"></i><span class="busuanzi-value" id="busuanzi_value_site_uv"></span></span><span class="site-pv"><i class="fa fa-eye"></i><span class="busuanzi-value" id="busuanzi_value_page_pv"></span></span></div></div></footer><div class="back-to-top"><i class="fa fa-arrow-up"></i></div></div><script type="text/javascript">"[object Function]"!==Object.prototype.toString.call(window.Promise)&&(window.Promise=null)</script><script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script><script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script><script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script><script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script><script type="text/javascript" src="/lib/canvas-nest/canvas-nest.min.js"></script><script type="text/javascript" src="/js/src/utils.js?v=5.1.0"></script><script type="text/javascript" src="/js/src/motion.js?v=5.1.0"></script><script type="text/javascript" src="/js/src/affix.js?v=5.1.0"></script><script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.0"></script><script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.0"></script><script type="text/javascript" src="/js/src/post-details.js?v=5.1.0"></script><script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.0"></script><script type="text/javascript">function proceedsearch(){$("body").append('<div class="popoverlay">').css("overflow","hidden"),$(".popup").toggle()}var isfetched=!1,search_path="search.xml";0==search_path.length&&(search_path="search.xml");var path="/"+search_path,searchFunc=function(e,t,a){"use strict";$.ajax({url:e,dataType:"xml",async:!0,success:function(e){isfetched=!0,$(".popup").detach().appendTo(".header-inner");var r=$("entry",e).map(function(){return{title:$("title",this).text(),content:$("content",this).text(),url:$("url",this).text()}}).get(),c=document.getElementById(t),n=document.getElementById(a);c.addEventListener("input",function(){var e=0,t='<ul class="search-result-list">',a=this.value.trim().toLowerCase().split(/[\s\-]+/);n.innerHTML="",this.value.trim().length>1&&r.forEach(function(r){var c=!1,n=r.title.trim().toLowerCase(),s=r.content.trim().replace(/<[^>]+>/g,"").toLowerCase(),o=decodeURIComponent(r.url),i=-1,l=-1,p=-1;if(""!=n&&a.forEach(function(e,t){i=n.indexOf(e),l=s.indexOf(e),(i>=0||l>=0)&&(c=!0,0==t&&(p=l))}),c){e+=1,t+="<li><a href='"+o+"' class='search-result-title'>"+n+"</a>";var h=r.content.trim().replace(/<[^>]+>/g,"");if(p>=0){var u=p-20,d=p+80;u<0&&(u=0),0==u&&(d=50),d>h.length&&(d=h.length);var f=h.substring(u,d);a.forEach(function(e){var t=new RegExp(e,"gi");f=f.replace(t,'<b class="search-keyword">'+e+"</b>")}),t+='<p class="search-result">'+f+"...</p>"}t+="</li>"}}),t+="</ul>",0==e&&(t='<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'),""==a&&(t='<div id="no-result"><i class="fa fa-search fa-5x" /></div>'),n.innerHTML=t}),proceedsearch()}})};$(".popup-trigger").click(function(e){e.stopPropagation(),0==isfetched?searchFunc(path,"local-search-input","local-search-result"):proceedsearch()}),$(".popup-btn-close").click(function(e){$(".popup").hide(),$(".popoverlay").remove(),$("body").css("overflow","")}),$(".popup").click(function(e){e.stopPropagation()})</script><script>!function(){var t=document.createElement("script"),e=window.location.protocol.split(":")[0];t.src="https"===e?"https://zz.bdstatic.com/linksubmit/push.js":"http://push.zhanzhang.baidu.com/push.js";var s=document.getElementsByTagName("script")[0];s.parentNode.insertBefore(t,s)}()</script></body></html>